package dynamicprogramming;

/**
 * @author kaho
 * @since 2021/2/19
 */
public class __01背包问题 {

    /**
     *
     * dp[i][j] 最大承重为j的前i件物品的最大价值
     * dp[0][j] = dp[i][0] = 0
     *
     * j<weight[i-1] ,dp[i][j] = dp[i-1][j]
     * j>=weight[i-1],dp[i][j] = max{dp[i-1][j], dp[i-1][j-weight[i-1]] +value[i-1]}
     *
     * @param values
     * @param weight
     * @param capacity
     * @return
     */
    int select(int[] values, int[] weight, int capacity){
        if (weight.length == 0 || values.length != weight.length || capacity <= 0) {
            return 0;
        }
        int[][] dp = new int[values.length+1][capacity+1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j>=weight[i-1]) {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+values[i-1]);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[values.length][capacity];
    }
}
